#include <iostream>
#include <string.h>

using namespace std;

static const int N = 10;
int a[N][N];

int lcs(string x, string y)
{
	int xl = x.length();
	int yl = y.length();
	a[0][0] = 0;
	for (int i = 1; i < xl; ++i)
	{
		a[i][0] = 0;
	}
	for (int j = 1; j < yl; ++j)
	{
		a[0][j] = 0;
	}

	for (int i = 1; i <= xl; ++i)
	{
		for (int j = 1; j <= yl; ++j)
		{
			if (x[i-1] == y[j-1])
			{
				a[i][j] = a[i-1][j-1] + 1;
			}
			else
			{
				a[i][j] = max(a[i-1][j], a[i][j-1]);
			}
		}
	}

	return a[xl][yl];	
}

int main()
{
	string x = "abcbdab";
	string y = "bdcaba";
	int ret = lcs(x, y);
	cout << ret << endl;
	return 0;
}
